let graph = [
  {
    vertex: 0,
    edges: [
      {
        adjVex: 1,
        weight: 6,
      },
      {
        adjVex: 2,
        weight: 4,
      },
      {
        adjVex: 3,
        weight: 5,
      },
    ],
  },
  {
    vertex: 1,
    edges: [
      {
        adjVex: 4,
        weight: 1,
      },
    ],
  },
  {
    vertex: 2,
    edges: [
      {
        adjVex: 4,
        weight: 1,
      },
    ],
  },
  {
    vertex: 3,
    edges: [
      {
        adjVex: 5,
        weight: 2,
      },
    ],
  },
  {
    vertex: 4,
    edges: [
      {
        adjVex: 6,
        weight: 9,
      },
      {
        adjVex: 7,
        weight: 7,
      },
    ],
  },
  {
    vertex: 5,
    edges: [
      {
        adjVex: 7,
        weight: 4,
      },
    ],
  },
  {
    vertex: 6,
    edges: [
      {
        adjVex: 8,
        weight: 2,
      },
    ],
  },
  {
    vertex: 7,
    edges: [
      {
        adjVex: 8,
        weight: 2,
      },
    ],
  },
  {
    vertex: 8,
    edges: [],
  },
];

function topo(g) {
  // 初始化逆邻接和入度
  g.forEach((e) => {
    e.inDegree = 0;
    e.contraryAdjv = [];
  });

  g.forEach((endV) => {
    g.forEach((startV) => {
      startV.edges.forEach((e) => {
        if (e.adjVex == endV.vertex) {
          endV.inDegree++;
          endV.contraryAdjv.push({
            vertex: startV.vertex,
            weight: e.weight,
          });
        } // 同时把逆邻接点求出
      });
    });
  });

  // 初始化栈，将入度为零的顶点压栈，即找到哪些顶点是没有前驱的
  // 删除顶点 -> 元素出栈， 删除该元素对应的弧 -> 邻接点的入度减一 （判断入度是否为零，如果为零，压栈 ）
  let stack = g.filter((e) => e.inDegree == 0);
  let res = [];
  // edges为空是否需要特殊处理
  while (stack.length) {
    let t = stack.pop();
    // console.log(t.vertex);
    res.push(t.vertex);
    t.edges.forEach((e) => {
      let v = g[e.adjVex];
      v.inDegree--;
      if (v.inDegree == 0) {
        stack.push(v);
      }
    });
  }

  return res;
}

let topoList = topo(graph); // 求得拓扑序列

// craticalPath j -> k

// ve[] 事件早发生时间 ve[0] = 0, ve[k] = max{ve[j] + len<vj, vk>}; 即逆邻接点的最晚时间 + 弧的权值
let ve = [];
topoList.forEach((e, index) => {
  if (index == 0) {
    ve.push(0);
  } else {
    let v = graph[e]; // v是一个顶点对象
    // console.log(v);
    let cost = 0;
    v.contraryAdjv.forEach((item) => {
      // item: { adjVex weight}
      let temp = ve[item.vertex] + item.weight;
      if(temp > cost) {
        cost = temp; // 选最大的
      }
    });
    ve[e] = cost;
  }
});
// console.log(ve);


// vl[] 事件最晚发生事件 vl[n] = ve[n] , vl[k] = min{ vl[j] - len<vk, vj>}
let vl = [];
// let n = ve.length - 1;
// vl[n] = ve[n];
let reverseTopoList = topoList.reverse();
reverseTopoList.forEach( (e, index) => {
  if(index == 0) {
    vl[e] = ve[e];
  } else {
    let cost = Infinity;
    let v = graph[e];
    v.edges.forEach(item => {
      let temp = vl[item.adjVex] - item.weight;
      if(temp < cost) {
        cost = temp;
      }
    })
    vl[e] = cost;
  }
})
// console.log(vl);

// 输入边集
let edges = [
  // a0
  {
    start: 0,
    end: 1,
    weight: 6 
  },
  {
    start: 0,
    end: 2,
    weight: 4 
  },
  {
    start: 0,
    end: 3,
    weight: 5
  },
  // a3
  {
    start: 1,
    end: 4,
    weight: 1 
  },
  {
    start: 2,
    end: 4,
    weight: 1 
  },
  // a5
  {
    start: 3,
    end: 5,
    weight: 2 
  },
  {
    start: 4,
    end: 6,
    weight: 9 
  },
  {
    start: 4,
    end: 7,
    weight: 7 
  },
  // a8
  {
    start: 5,
    end: 7,
    weight: 4 
  },
  {
    start: 6,
    end: 8,
    weight: 2 
  },
  {
    start: 7,
    end: 8,
    weight: 2 
  }
]
// 如何求活动的   最晚发生时间 和 最早发生时间？ ai 的序号？？？
// ee[] 活动最早开始事件
let ee = [], el = [];
let ca = []; // cracticalActivity 关键活动
for(let i = 0; i < edges.length; i++) {
  ee[i] = ve[edges[i].start];
  el[i] = vl[edges[i].end] - edges[i].weight;
  if(ee[i] == el[i])
    ca.push(i)
}
console.log(ee);
console.log(el);
console.log(ca);



